package leetcode.hot100;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;

/**
 * @author kl liu
 * @description
 * @date 2021/8/10 2:51 下午
 */
@SuppressWarnings("all")
public class _448_找到所有数组中消失的数字_集合 {

    /**
     * 给你一个含 n 个整数的数组 nums ，其中 nums[i] 在区间 [1, n] 内
     * 请你找出所有在 [1, n] 范围内但没有出现在 nums 中的数字，并以数组的形式返回结果
     */
    public List<Integer> findDisappearedNumbers(int[] nums) {
        List<Integer> result = new ArrayList<>();
        if (nums == null || nums.length == 0) return result;
        // 用一个集合记录数组 nums 中的数字
        HashSet<Integer> set = new HashSet<>();
        for (int num : nums) {
            set.add(num);
        }
        // 由于数字范围均在 [1,n] 中，记录数字后我们再利用集合检查 [1,n] 中的每一个数是否出现，从而找到缺失的数字
        for (int i = 1; i <= nums.length; i++) {
            if (!set.contains(i)) {
                result.add(i);
            }
        }
        return result;
    }
}
